//////////////////////////////////////////////////////////////////////
// Octree.h
//
// WANG Yangzihao
// slashspirit@gmail.com
//
// Copyright (C) WANG Yangzihao, 2011, All rights reserved.
//////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////
//  Brief Description
//
//	Linear Octree Class: Based on the octree class in Klay Game Engine (http://www.klayge.org)
//
//////////////////////////////////////////////////////////////////////
#pragma once
#include <SceneGraph.h>
#include <BoundingBox.h>
#include <LA/Plane.h>
#include <boost/pool/pool_alloc.hpp>
#include <queue>
#include <Frustum.h>

namespace grflib
{
    namespace engine
    {
        namespace aux
        {
            template<typename TObj, typename TRenderQueue>
            class COctree : public grflib::engine::core::CSceneGraph<TObj, TRenderQueue>
            {
            public:
                explicit COctree(void);
                virtual ~COctree(void);

                //object management
                virtual bool AddObj(boost::shared_ptr<TObj> &pObj);
                virtual void RemoveObj(boost::shared_ptr<TObj> &pObj);
                virtual void Clear(void);

                //rebuild tree
                virtual void NotifySceneUpdate(void);
                virtual void Update(void);

                //generate rendering queue according to viewer/obj positions
                virtual void GenerateRenderQueue(TRenderQueue &renderQueue, 
                                                 const D3DXMATRIX *pViewMat,
                                                 const D3DXMATRIX *pProjMat);

                //given a ray, find the first intersected object in the octree
                //if no intersection, return null
                virtual boost::shared_ptr<TObj> GetIntersectedObj(const float3& src, const float3& dir);

                //traverse interface
                virtual HRESULT Traverse(const grflib::engine::core::IMemberCaller<TObj>& func);
                //virtual HRESULT Traverse(const grflib::engine::core::IMemberPtrCaller<TObj>& func);

                //get/update maximum tree depth
                inline void SetMaxTreeDepth(UINT max_tree_depth)
                { m_max_tree_depth = std::min<UING>(max_tree_depth, 16UL); }
                inline UINT GetMaxTreeDepth(void) const { return m_max_tree_depth; }

                //set rebuild tree flag
                inline void ForceRebuildOnNextFrame(void) { m_rebuild_tree = rebuild; }

            protected:
                //private methods
                bool RayBBoxIntersectTest(const float3& src, const float3& dir, const grflib::engine::core::BBox<float>& box) const;
				void NodeVisibilityTest(size_t index, const grflib::engine::core::CFrustum &frustum);

            protected:
                //data members

                //Scene Objects
                std::vector< boost::shared_ptr<TObj> > m_store;
				std::vector<bool> m_in_render_queue;

                //Octree Node Struct for octree scene manager operations
                struct octree_node_s
                {
                    grflib::engine::core::BBox<float> bb;
                    int first_child_index;
                    std::vector<size_t> obj_indices;
                    uint32_t depth;
                    grflib::engine::core::CFrustum::VIS vis;
                };

                std::vector<octree_node_s, boost::pool_allocator<octree_node_s> > m_octree;
                std::vector<size_t, boost::pool_allocator<size_t> > m_base_address;

                UINT m_max_tree_depth;
                bool m_rebuild_tree;
            };
        } //namespace aux
    } //namespace engine
} //namespace grflib

#include <OctreeImpl.hpp>